package com.algorithm.learning.base.动态规划;

/**
 * @program: algorithm-learning
 * @description:
 * @author: YuKai Fan
 * @create: 2024/9/4 21:14
 **/
public class N皇后问题 {

    public static void main(String[] args) {
        int n = 3;
        int[] nums = new int[n];
        System.out.println(process(0, nums, n));
    }

    /**
     * N皇后问题是指在N*N的棋盘上要摆N个皇后，
     * 要求任何两个皇后不同行，不同列，也不在同一条斜线上
     *
     *
     * 给定一个整数n，返回n皇后的摆法有多少种
     * n=1，返回1
     * n=2或3，,2皇后和3皇后问题无论怎么摆都不行，返回0
     * n=8，返回92
     *
     * @param i 这里i表示当前需要放皇后的行数
     * @param record 记录i之前的皇后位置，其中下标就表示行位置，下标对应的值就表示列位置
     * @param n  皇后数
     */
    public static int process(int i, int[] record, int n) {
        // 如果i==n，就表示i之前的所有情况都成立，那么就表示是整个棋盘，存在一种方案，直接返回1
        if (i == n) {
            return 1;
        }
        int res = 0;
        // 这里的j，表示放皇后的列数
        for (int j = 0; j < n; j++) {
            // 当前i行的皇后，放在j列，会不会和之前(0..i-1)的皇后，不共行或者共斜线，
            // 如果是，则认为有效
            // 如果不是，则认为无效
            if (isValid(record, i ,j)) {
                // 这里把当前i的值，直接赋值为j，实际上就是一种还原现场
                //
                record[i] = j;
                res += process(i + 1, record, n);
            }
        }
        return res;
    }

    // record[0..i-1]需要看，record[i...] 不需要看
    // 返回i行皇后，放在了j列，是否有效

    /**
     * 是否有效分为两个部分：
     * 1. 首先判断是否存在同列的
     *      1.1 对于是否同列很简单，record[i]这个值，就表示当前i行之前的所有皇后的列位置，所以只要遍历0~i-1的值，判断是否相等即可
     *      也就是for(k=0, k<i, k++) j == record[k]
     * 2. 在判断是否存在皇后在一条斜线上
     *      2.1 对于判断两个及以上的皇后是否在一条斜线上，假设两个皇后的坐标（行, 列）如下
     *          (a, b)、(c, d)只要 |a-c| == |b-d|这个条件成功，那么就表示在一条斜线上
     * @param record
     * @param i
     * @param j
     * @return
     */
    private static boolean isValid(int[] record, int i, int j) {
        for (int k = 0; k < i; k++) {// 之前的某个k行的皇后
            if (j == record[k] || Math.abs(record[k] - j) == Math.abs(i - k)) {
                return false;
            }
        }
        return true;
    }

    /**
     * 基于int做位运算解决N皇后问题
     *
     * 不能超过32皇后问题
     * @param n
     * @return
     */
    public static int num2(int n) {
        if (n < 1 || n > 32) {
            return 0;
        }
        int limit = n == 32 ? -1 : (1 << n) - 1;
        return process2(limit, 0, 0, 0);
    }

    /**
     * N皇后优化版，整体思路不变，用位运算优化到常数时间
     * @param limit 固定的值，比如8皇后的限制，就是1 << 8 - 1
     * @param colLim 列的限制，1的位置不能放皇后，0的位置可以
     * @param leftDiaLim 左斜线的限制，1的位置不能放皇后，0的位置可以
     * @param rightDiaLim 右斜线的限制，1的位置不能放皇后，0的位置可以
     * @return
     */
    public static int process2(int limit, int colLim, int leftDiaLim, int rightDiaLim) {
        if (colLim == limit) {
            return 1;
        }
        // 所有候选皇后的位置，都在pos上
        // colLim | leftDiaLim | rightDiaLim -> 总线制, 即列上是否1，左斜线上是否1，右斜线上是否1
        // ~(colLim | leftDiaLim | rightDiaLim) -> 左侧的所有0全部变成1，右侧每个1，变成可尝试的位置
        int pos = limit & (~(colLim | leftDiaLim | rightDiaLim));
        int mostRightOne = 0;
        int res = 0;
        while (pos != 0) {
            // 提取出pos中，最右侧的1，剩下位置都是0
            mostRightOne = pos & (~pos + 1);
            pos = pos - mostRightOne;
            res += process2(limit,
                    colLim | mostRightOne,
                    (leftDiaLim | mostRightOne) << 1,
                    (rightDiaLim | mostRightOne) >>> 1);
        }
        return res;
    }
}
